package com.zj.leetcode.medium;

/**
 * @program: algorithm
 * @description: 扁平化多级双向链表
 * 430 flatten-a-multilevel-doubly-linked-list
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class FlattenAMultilevelDoublyLinkedList {
    public static void main(String[] args) {
        Solution solution = new FlattenAMultilevelDoublyLinkedList().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

    static class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }


    class Solution {
        public Node flatten(Node head) {

            dfs(head);
            return head;

        }

        public Node dfs(Node head) {
            Node cur = head;

            Node last = null;

            while (cur != null) {
                Node next = cur.next;

                if (cur.child != null) {
                    cur.next = cur.child;
                    Node childLast = dfs(cur.child);
                    cur.child.prev = cur;

                    cur.child = null;
                    cur = childLast;
                    cur.next = next;
                    if(next != null){
                        next.prev = cur;
                    }

                } else {
                    if (cur.next == null) {
                        last = cur;
                    }
                    cur = cur.next;
                }
            }

            return last;
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}
